#include <dbg.h>
#include <gtest/gtest.h>
using namespace std;

class Solution {
public:
    void dfs(vector<vector<int>>& isConnected,
             vector<int>& visited,
             int cities,
             int i) {
        for (int j = 0; j < cities; j++) {  // 遍历与当前城市直接相连的其他城市
            if (isConnected[i][j] == 1 &&
                !visited[j]) {   // 如果当前城市与其他城市直接相连且未被访问过
                visited[j] = 1;  // 标记为已访问
                dfs(isConnected, visited, cities, j);  // 递归搜索其他城市
            }
        }
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        int cities = isConnected.size();  // 城市数量
        vector<int> visited(cities);      // 标记城市是否被访问过

        int provinces = 0;
        for (int i = 0; i < cities; i++) {             // 遍历每个城市
            if (!visited[i]) {                         // 如果当前城市未被访问过
                dfs(isConnected, visited, cities, i);  // 从当前城市开始 dfs
                ++provinces;                           // 省份数量加1
            }
        }

        return provinces;
    }
};

TEST(findCircleNum, test1) {
    Solution s;

    vector<vector<int>> isConnected = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
    EXPECT_EQ(s.findCircleNum(isConnected), 2);
}

TEST(findCircleNum, test2) {
    Solution s;

    vector<vector<int>> isConnected = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
    EXPECT_EQ(s.findCircleNum(isConnected), 3);
}

int main(int argc, char** argv) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}